# 15. 三数之和
from typing import List


def threeSum(nums: List[int]) -> List[List[int]]:
    # 排序好数组
    nums.sort()
    print(f"sort_nums:{nums}")
    re = []
    for index, value in enumerate(nums):
        # 避免超时，避免重复判断
        if value > 0:
            break

        # 避免超时，避免全部为0的数字
        if re and re[-1][0] == value:
            continue

        # 使用双指针的方式
        left_index = index + 1
        right_index = len(nums) - 1

        while left_index < right_index:
            if left_index == index:
                left_index += 1
            if right_index == index:
                right_index -= 1

            # 可能会相等
            if left_index == right_index:
                continue

            # 两数之和
            left_num = nums[left_index]
            right_num = nums[right_index]

            if left_num + right_num + value == 0:
                temp_re = [value, left_num, right_num]
                # 和上一个答案进行比较，避免超时
                if not re or re[-1] != temp_re:
                    re.append(temp_re)
                left_index += 1
                right_index -= 1
            elif (left_num + right_num + value) > 0:
                right_index -= 1
            else:
                left_index += 1
    return re


nums_1 = [-1, 0, 1, 2, -1, -4]
result = threeSum(nums_1)
print(f"result:{result}")

nums_2 = [-1, 0, 1, 0]
result = threeSum(nums_2)
print(f"result:{result}")

nums_3 = [-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4]
result = threeSum(nums_3)
print(f"result:{result}")

nums_3 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
result = threeSum(nums_3)
print(f"result:{result}")
